package org.laizili.solution.leetcode;

import java.util.Arrays;

/**
 * <a href="https://leetcode.cn/problems/find-k-th-smallest-pair-distance/">719. 找出第 K 小的数对距离</a>
 */
public class Problem719 {
    // submitted time: 2022年6月15日13:20:40
    private static class Solution {
        public int smallestDistancePair(int[] nums, int k) {
            Arrays.sort(nums);
            int max = nums[nums.length - 1] - nums[0];
            // 二分枚举 absolute distance
            int left = 0, right = max;
            while (left <= right) {
                int count = 0;
                int midDistance = left + ((right - left) >> 1);
                // 计数
                // 二分计数 + （TODO: 滑动窗口计数）
                for (int j = 1; j < nums.length; j++) {
                    int i = binarySearchBottom(nums, j, nums[j] - midDistance);
                    count += j - i;
                }
                if (count < k) {
                    left = midDistance + 1;
                } else {
                    right = midDistance - 1;
                }
            }
            return left;
        }

        private int binarySearchBottom(int[] nums, int upper, int remained) {
            int left = 0;
            int right = upper - 1;
            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                if (nums[mid] < remained) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return left;
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution().smallestDistancePair(new int[]{1, 6, 1}, 3));
    }
}
